The present invention relates generally to apparatus for producing code words and relates more particularly to such apparatus where such apparatus is responsive to the binary information content in an information bearing document.
A primary environment in which the present invention finds use is with facsimile machines. Facsimile machines are useful for transmitting a document or picture from a first location to a second location over communication lines such as telephone lines without the necessity of physically transporting the document or picture. Such facsimile machines scan the information bearing document on a line-by-line basis. The Facsmile machines then produce a particular code indicative of the information content of the document or picture. The code (or subsequent result of that code) is then sent over communication lines, as for example telephone lines, to a similar facsimile machine. The second facsimile machine then interprets the code received and reproduces the original document or picture.
The scanning of the information bearing document, the definition of the transmitted codes, the transmission of the codes, and the printing of the copy of the document are all standard known elements in facsimile machines. The transmitted codes are defined by International Telegraph and Telephone Consultative Committee (CCITT) Specifications. All facsimile machines adhering to this specification can then decode the information and reconstruct the original information bearing document.
CCITT codes are transmitted between one of several varities of facsimile machines. The present invention is primarily involved with producing code words which can ultimately result in CCITT Group 3 codes or rather those codes required of a CCITT Group 3 facsimile machine. Group 3 codes are defined in two varieties; namely one dimensional (1D) codes and two dimensional (2D) codes. 1D Codes interpret the information content of one line, namely the current line, being scanned and the code produced is indicative of the serial run lengths of the information contained therein and result in Huffman codes being produced. 2D Codes interpret not only the current line but also are dependent upon the information content of a previous line, usually the previous line scanned.
2D Codes compress the information content of an information bearing document into a fewer number of bits than 1D codes resulting in decreased transmission times. While encoding a document containing printing or graphical information, on many occasions a vertical or other vertically correlated edge (or line) will be present in the document. In order to accurately reflect these vertical correlations, it is advantageous to compare the vertical correlation of a change in the binary information content of a current line with a change in the binary information content of a previous line (usually the prior line).
For purposes of the present invention the scanning of a document is accomplished on a line-by-line basis. Each line is divided into a predetermined number of elements called picture elements. The information bearing document or picture is scanned and encoded in a binary (i.e. black and white) basis. All discrete picture elements (PELs) are represented as either black or white (with representation in binary language of either a 1 or a 0). A change in the binary information content of the information bearing document is a change (black to white, e.g. 1 to 0, or white to black, e.g. 0 to 1) in the representation of the color (black or white) of the picture element currently being scanned (the current picture element) from the color (black or white) of the picture element of the last scanned picture element (prior picture element). Hence a color change refers to a change in the color (black and white) of the picture elements.
2D Codes represent encoding of the vertical correlation between a color change between picture elements in the current line with a color change between picture elements in a prior line, usually the previous line. Such vertical correlation may be exactly vertical or the correlation may be within a certain predetermined range of vertical. In a typical facsimile machine encoding situation, a "window" is defined by examining vertical correlation of within three horizontal (if the document is being scanned horizontally) picture elements. Thus the "vertical correlations" considered are a "vertical 0 (V0)" with a color change in a previous line exactly vertical with a color change in the current line, "vertical left 3 (VL3)" with a color change in a prior line occurring three elements to the left of a color change in the current line, and correspondingly a "vertical left 2 (VL2)", a "vertical left 1 (VL1)", a "vertical right 1 (VR1)", a "vertical right 2 (VR2)" and a "vertical right 3 (VR3)".
Further, 2D codes require the outputting of "run length codes" indicative of the number of picture elements without a color change when there is no vertical correlation within the predetermined window in a prior line, usually a previous line. For purposes of this invention, no vertical correlation means no vertical correlation within the predetermined window as specified above. This mode of operation is usually known as horizontal (when the document is scanned horizontally) run length mode (HRM).
The encoding apparatus or machine needs to consider therefore the current picture element (since it knows if a color change has just occurred), seven previous line picture elements (VL3, VL2, VL1, V0, VR1, VR2 and VR3) in addition to whether the coding is in horizontal run length mode (HRM). This makes the code produced combinationally dependent upon nine separate and independent inputs. A combinational logic circuit to produce a code word dependent upon these nine separate independent inputs would require a circuit capable of handling 2.sup.9 or 1,024 different combinations. A combinational logic element capable of these differing combinations would be complex and, more importantly, may be relatively slow due to the number of cascaded logic levels through the combinational circuit.